We present a quantum algorithm for approximating the linear structures of aBoolean function $f$. Different from previous algorithms (such as Simon's andShor's algorithms) which rely on restrictions on the Boolean function, ouralgorithm applies to every Boolean function with no promise. Here, our methodsare based on the result of the Bernstein-Vazirani algorithm which is toidentify linear Boolean functions and the idea of Simon's period-findingalgorithm. More precisely, how the extent of approximation changes over thetime is obtained, and meanwhile we also get some quasi linear structures ifthere exists. Next, we obtain that the running time of the quantum algorithm tothoroughly determine this question is related to the relative differentialuniformity $\delta_f$ of $f$. Roughly speaking, the smaller the $\delta_f$ is,the less time will be needed.
展开▼
机译：我们提出了一种量子算法，用于近似布尔函数$ f $的线性结构。与以前的算法（例如Simon和Shor的算法）依赖于布尔函数的限制不同，我们的算法适用于每个没有保证的布尔函数。在这里，我们的方法基于伯恩斯坦-瓦兹拉尼算法的结果，该算法可识别线性布尔函数和西蒙的周期查找算法。更准确地说，获得了近似程度随时间变化的方式，同时，如果存在，我们还得到了一些准线性结构。接下来，我们得出量子算法的运行时间来彻底确定该问题与$ f $的相对微分均匀度$ \ delta_f $有关。粗略地说，$ \ delta_f $越小，所需的时间就越少。
展开▼
